package com.jiang.专题.动态规划.Q72;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/09 17:06
 */
class Solution {
    // 解决思路： 理解编辑含义 -> 发现子问题（状态转移）-> 模式识别(解决方式) -> 根据状态转移写出状态转移方程 -> 代码编写 -> 优化（像递归可以用一个记忆（memoization）数组保存计算的结果， 计算过就直接返回）

    // 动态规划（自底向上）
    // public int minDistance(String word1, String word2) {
    //     int len1 = word1.length();
    //     int len2 = word2.length();

    //     int[][] dp = new int[len1 + 1][len2 + 1]; // dp[i][j] 表示word1的前i个字符转换成word2的前j个字符所使用的最少操作数
    //     // 当word1的长度为0时，只能进行插入操作，操作数为j
    //     for (int j = 1; j <= len2; j++) {
    //         dp[0][j] = j;
    //     }

    //     // 当word2的长度为0时，只能进行删除操作，操作数为i
    //     for (int i = 1; i <= len1; i++) {
    //         dp[i][0] = i;
    //     }

    //     for (int i = 1; i <= len1; i++) {
    //         for (int j = 1; j <= len2; j++) {
    //             // word1的第i个字符与word2的第j个字符不一样的三个操作
    //             int add = dp[i][j - 1]; // 进行插入操作，在word1的第i个字符后面加一个word2第j个字符， 就要找到{i字符==j-1字符}子问题
    //             int del = dp[i - 1][j]; // 进行删除操作，删除word1的第i个字符， 就要找到 {i-1字符== j字符}状态转移
    //             int rep = dp[i - 1][j - 1]; // 进行替换操作，将word1的第i个字符替换为word2的第j个字符， 就要找到{i-1字符==j-1字符}；  如果第i个字符与第j个字符一样，也需要找到{i-1字符==j-1字符}
    //             if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
    //                 dp[i][j] = rep;
    //             } else {
    //                 dp[i][j] = Math.min(add, Math.min(del, rep)) + 1;
    //             }
    //         }
    //     }
    //     return dp[len1][len2];
    // }

    // 递归（自顶向下）
    // public int minDistance(String word1, String word2) {
    //     // 记忆数组，防止重复计算（这里不做初始是因为递归中判断了长度为0的情况[第一行第一列为0]）
    //     int[][] memoization = new int[word1.length() + 1][word2.length() + 1];
    //     char[] w1 = word1.toCharArray();
    //     char[] w2 = word2.toCharArray();
    //     return minDistance(w1, w2, w1.length, w2.length, memoization);
    // }

    // public int minDistance(char[] word1, char[] word2, int len1, int len2, int[][] memoization) {
    //     // word1或word2长度为0，只做增加或删除
    //     if (len1 == 0 || len2 == 0) {
    //         return Math.max(len1, len2);
    //     }

    //     // 如果记忆数组中的值不为0，说明计算过，直接返回
    //     if (memoization[len1][len2] != 0) {
    //         return memoization[len1][len2];
    //     }

    //     // 如果最后一个字符相等，则看len1 - 1和len2 - 1两个字符
    //     if (word1[len1 - 1] == word2[len2 - 1]) {
    //         return memoization[len1][len2] = minDistance(word1, word2, len1 - 1, len2 - 1, memoization);
    //     }

    //     // 不同，找出三种操作最小值 + 1
    //     return  memoization[len1][len2] = 1 + Math.min(minDistance(word1, word2, len1, len2 - 1, memoization), Math.min(minDistance(word1, word2, len1 - 1, len2, memoization), minDistance(word1, word2, len1 - 1, len2 - 1, memoization)));
    // }


    // 一维动态规划优化
    public int minDistance(String word1, String word2) {
        return edit(word1.toCharArray(), word2.toCharArray(), 1, 1, 1);
    }

    private int edit(char[] ss1, char[] ss2, int add, int remove, int update) {
        int row = ss1.length, column = ss2.length;
        int[] dp = new int[column + 1];
        for (int i = 1; i <= column; i++) {
            dp[i] = i * add;
        }
        for (int i = 1, leftUp; i <= row; i++) {
            leftUp = (i - 1) * remove; // 在j为1时的左上角
            dp[0] = i * remove; // 在j为1时用到
            for (int j = 1, backup; j <= column; j++) {
                backup = dp[j]; // dp[j]此时还是上边， 在下一次循环时为左上角
                if (ss1[i - 1] == ss2[j - 1]) {
                    dp[j] = leftUp;
                } else {
                    dp[j] = Math.min(Math.min(leftUp + update, dp[j - 1] + add), dp[j] + remove);
                }
                leftUp = backup;
            }
        }
        return dp[column];
    }
}
